<h1>bias</h1>

<ul>
<li> <a href="#1">Code</a>
<ul>
<li> <a href="#2">Uses</a>
<li> <a href="#3">Top-level Drivers</a>
<ul>
<li> <a href="#4">sample</a>
<li> <a href="#5">sampleCounts</a>
</ul>
<li> <a href="#6">Workers</a>
<ul>
<li> <a href="#7">a2cdf</a>
<li> <a href="#8">a2best</a>
<li> <a href="#9">sorted2cdf</a>
<li> <a href="#10">Pick</a>
</ul>
</ul>
<li> <a href="#11">Author</a>
</ul>
<p>
Given a frequency counts of a population, generate numbers biased by those frequencies.
For demo of this code, see <a href="demoBias">demoBias</a>.
</p>
<a name="1"></a><h2>Code</h2>

<a name="2"></a><h3>Uses</h3>
<p>
<a href="?o">o</a> <a href="?math">math</a> <a href="?s2a">s2a</a> 
</p>
<a name="3"></a><h3>Top-level Drivers</h3>

<a name="4"></a><h4>sample</h4>
<p>
Sample from population of things.
</p>
<pre>
 function sample(population,cdf,memo,   count,one) { 
     for(one in population) 
         count[population[one]]++
     return sampleCounts(count,cdf,memo)
 }
</pre>
<a name="5"></a><h4>sampleCounts</h4>
<p>
Sample of a list of counted things.
</p>
<pre>
 function sampleCounts(counts,cdf,memo,   all, one,x,f,i) {
     for(one in counts)
         all += counts[one]
     for(one in counts) {
         x = (1000*counts[one]/all)+ rand()/100
         f[++i]= x
         memo[x] = one
     }
     a2cdf(f,cdf)
     return i
 }
</pre>
<a name="6"></a><h3>Workers</h3>

<a name="7"></a><h4>a2cdf</h4>
<p>
Prepare an array of numbers, prior to picking. 
Internally, this code 
converts an array of numbers into a cdf. From
<a href="http://www.aiaccess.net/English/Glossaries/GlosMod/e<em>gm</em>distribution_function.htm">aiaccess.net</a>: 
</p>
<ul>
<li> A <em>cdf</em> (or "cumulative distribtion function") is the proportion of the population whose value is less than x.  The <em>cdf</em> of  a random variable is clearly a monotonously increasing (or more precisely, non decreasing) function from 0 to 1.
</ul>
<p>
In Awk, we can represent this as an array of  "<em>n</em>" symbols stored at
locations 1,2,3..n and a set of increasing probabilities  locations
-1,-2,-3,...-n (where -i is the probability of symbol i). 
</p>
<pre>
 function a2cdf(a,cdf, sorted,n) {
     n= a2best(a,sorted)
     return sorted2cdf(n,sorted,cdf)
 }
</pre>
<a name="8"></a><h4>a2best</h4>
<p>
If "<em>a</em>" is an array of numbers,  then sort them in ascending order.
If <em>max</em> is supplied, return no more than the first <em>max</em> number of values. 
</p>
<pre>
 function a2best(a,best,  max,    sorted,n,i,j) {
                #must     opt     local
     n = asort(a,sorted);
     if (max && n >= max) {
         for(i = n - max + 1; i&lt;=n; i++)
             best[++j] = sorted[i];
         n= max;
     } 
     else 
         for(i in sorted)
             best[i]=sorted[i];
     return n;
 }
</pre>
<a name="9"></a><h4>sorted2cdf</h4>
<pre>
 function sorted2cdf(n,sorted,cdf,    i,j,sum) {
     if (! (1 in sorted)) 
         return (cdf[0]=split("",cdf,""))
     sum = cdf[1] = sorted[1];
     for(i=2;i&lt;=n;i++) { 
         sum += sorted[i];
         cdf[i] = cdf[i-1] + sorted[i];
     }
     for(i in cdf)  
         cdf[i] = cdf[i] / sum;
     for(i=1;i&lt;=n;i++)
         cdf[-1*i] = sorted[i]
     cdf[0]=n
     return n
 }
</pre>
<a name="10"></a><h4>Pick</h4>
<p>
Return one symbol from a <em>cdf</em>, biased by the <em>cdf</em> probabilities. 
If <em>skew</em> is provided, bias the selection towards one end of the
distribtion. The larger the <em>skew</em> (above one), the more we favor
things with higher probabilities. It <em>skew</em> is one, the just
draw from the supplied distribution.
</p>
<pre>
 function pick(cdf,  skew,   i) {
               #must   opt     local
     i = pick1(cdf,cdf[0],skew)
     return cdf[-1*i]
 }
 function pick1(cdf,n,  skew,u,i,here) {
     skew = skew ? skew : 1
     u = rand()^skew 
     for(i=n-1;i>=1;i--) 
         if (u > cdf[i] ) 
             return i+1;
     return 1;
 }
</pre>
<a name="11"></a><h2>Author</h2>
<p>
Tim Menzies
